#!/usr/bin/python3
import sys
import heapq

def parse(lines):
    return tuple([tuple([int(n) for n in line]) for line in map(tuple, map(str.strip, lines))])

def find(grid, bounds, start):
    offset = ((1, 0), (0, -1), (-1, 0), (0, 1))
    nodes = []
    heapq.heappush(nodes, start)
    seen = set()
    while len(nodes) > 0:
        node = heapq.heappop(nodes)
        print(node)
        heat, x, y, dx, dy, run = node
        if x == bounds[1] - 1 and y == bounds[0] - 1:
            return heat
        heatless = (x, y, dx, dy, run)
        if any([True for r in range(run + 1) if (x, y, dx, dy, r) in seen]):
            continue
        seen.add(heatless)
        for ox, oy in offset:
            if dx == -ox and dy == -oy:
                continue
            nx = x + ox
            ny = y + oy
            straight_run = ox == dx and oy == dy
            nr = run + 1 if straight_run else 0
            if nx < 0 or nx >= bounds[1] or ny < 0 or ny >= bounds[0]:
                continue
            if run >= 2 and straight_run:
                continue
            heapq.heappush(nodes, (heat + grid[ny][nx], nx, ny, ox, oy, nr))

def find2(grid, bounds, starts):
    offset = ((1, 0), (0, -1), (-1, 0), (0, 1))
    nodes = []
    for start in starts:
        heapq.heappush(nodes, start)
    seen = set()
    while len(nodes) > 0:
        node = heapq.heappop(nodes)
        print(node)
        heat, x, y, dx, dy, run = node
        if x == bounds[1] - 1 and y == bounds[0] - 1 and run >= 4:
            return heat
        heatless = (x, y, dx, dy, run)
        if heatless in seen:
            continue
        seen.add(heatless)
        for ox, oy in offset:
            if dx == -ox and dy == -oy:
                continue
            nx = x + ox
            ny = y + oy
            straight_run = ox == dx and oy == dy
            nr = run + 1 if straight_run else 0
            if nx < 0 or nx >= bounds[1] or ny < 0 or ny >= bounds[0]:
                continue
            if run >= 10 and straight_run:
                continue
            if run <= 3 and not straight_run:
                continue
            heapq.heappush(nodes, (heat + grid[ny][nx], nx, ny, ox, oy, nr))

def part1():
    print('part 1')
    grid = parse(sys.stdin.readlines())
    bounds = (len(grid), len(grid[0]))
    start = (0, 0, 0, 0, 0, 0)
    print(find(grid, bounds, start))

def part2():
    print('part 2')
    grid = parse(sys.stdin.readlines())
    bounds = (len(grid), len(grid[0]))
    start1 = (0, 0, 0, 1, 0, 0)
    start2 = (0, 0, 0, 0, 1, 0)
    print(find2(grid, bounds, [start1, start2]))

if sys.argv[1] in '1':
    part1()
else:
    part2()
